package day45_other248;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/23 20:50
 * @Version 1.0
 */
public class Solution {
    public int[] solve(Tree root) {
        //map存储结点和结点对应的列索引，方便层序遍历时的查找
        HashMap<Tree, Integer> map = new HashMap<>();
        //hashmap记录每列的索引，以及该列的第一个元素
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //queue用于层序遍历
        Queue<Tree> queue = new LinkedList<>();
        //记录根节点
        queue.offer(root);
        map.put(root, 0);
        hashMap.put(0, root.val);
        //记录最小的索引号
        int minValue = 0;


        while (!queue.isEmpty()){
            Tree poll = queue.poll();
            int col = map.get(poll);

            if (poll.left != null){
                map.put(poll.left, col - 1);
                //记录每列第一个元素
                if (!hashMap.containsKey(col - 1)){
                    hashMap.put(col - 1, poll.left.val);
                }
                minValue = Math.min(minValue, col - 1);
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                map.put(poll.right, col + 1);
                //记录每列第一个元素
                if (!hashMap.containsKey(col + 1)){
                    hashMap.put(col + 1, poll.right.val);
                }
                queue.offer(poll.right);
            }
        }
        //将hashmap中的数据转换成数组输出
        int[] res = new int[hashMap.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = hashMap.get(minValue);
            minValue++;
        }
        return res;
    }
}
